// 时间复杂度是 O(N)  // 用数学的错位相减法
// 空间复杂度是
public class TestHeap {
    // 大根堆的实现
    // (想要修改成小根堆的话就是把里面的大于号小于号改一改就行了)
    public int[] elem;
    public int usedSize;

    public TestHeap(){
        this.elem = new int[10];
    }


    // 初始化数组
    public void initElem(int[] array){
        for(int i = 0; i < array.length; i++){
            elem[i] = array[i];
            usedSize++;
        }
    }
    // 创建一个堆
    public void creatHeap(){
        // 建一个大堆为例
        // 每次调整的时候都是左右孩子的最大值跟根节点去比较

        // 已知孩子节点的下标 i 其父亲节点的下标为  (i-1)/2
        // 而在这里面的 ， 最后一个节点的父亲节点的下标可以这样求：(len - 1 - 1) / 2 (len是数组的长度)
        for (int parent = (usedSize -1-1)/2; parent >=0 ; parent--){
            // 从最后一个节点开始往前调整
            shiftDown(parent,usedSize); // 这里面传useSize是表示所求的最后一个元素不可能超过这个数组长度
        }

    }

    // 所以把每棵树的调整抽象出来一个函数
    // 这个函数写的是向下调整 意思是 每一颗树的调整都是从父亲节点开始往下调整

    /**
     *
     * @param parent 父亲下标
     * @param len 每棵树结束的下标
     */
    private  void shiftDown(int parent,int len){
        int child = 2*parent+1 ; // 需要定义一个左孩子节点的下标，不需要右孩子的，因为左孩子的下标就可以知道所求的是否越界
        // 最起码要有左孩子
        while(child < len){
            if( child+1 < len && elem[child] < elem[child+1]){ // 在有右孩子的情况下这样写
                child++;  //这样能满足 child 的下标一定是左右孩子 最大值下标
            }
            // 然后判断父亲节点和子节点值的大小
            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;  // 到这里还没有结束
                // 交换完之后 继续向下判断这个根节点跟下面的比较
                parent = child;
                child = 2*parent+1;
            }else {
                break;  // 走到else的话是说明已经调整完了，不许要再调了，因为我们是从下面往上开始调的

            }
        }
    }

// 堆的插入与删除
    // 向上调整
    // 向上调整的时间复杂度: O(N*logN)
    //需要已知孩子节点来求父亲节点
    // 先插入到最后一个节点的位置，只需要比较父亲节点的值不需要比较左右节点的

    //插入

    // 向上调整
    private void shiftUp(int child){
        // 传入孩子节点的位置
        // 然后 根据孩子节点的位置来判读父亲节点
        int parent = (child - 1) / 2;
        while(child > 0){   // 以 child > 0 来判断什么时候结束
            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child - 1)/2;
            }else {
                break;
            }
        }
    }
    public void offer(int val){
        // 判断空不空 和 满不满
        if(isFull()){ // 开始扩容
           elem =  Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;  //在最后一个位置存放val   // 此时usedSize == 11
        // 放置完之后开始进行向上调整
        shiftUp(usedSize-1);  // 把 10 传进去

    }
    public boolean isFull(){
        return usedSize == elem.length;
    }


   //堆的删除
    // 一定是去删除堆顶元素
    // 还是以大根堆为例
    // 做法是将第一个元素和最后一个元素进行交换
    // 这样就可以控制元素删除了
    // 因为 usedSize 的 大小我们是可以控制的
    // 边成了一个只有根节点不是大根堆的节点
    // 此时只需要调整0下标的数就可以了
    public void pop(){
        // 先判断是否为空
        if (isEmpty()){
            return;
        }
        //然后交换0 下标 和 usedSize - 1 下标的元素
        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        // 然后把最后一个删除
        usedSize--;
        // 然后进行向下调整
        shiftDown(0,usedSize);
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }

    // 堆的 peek
    public int peek(){
        // 先判断是否为空
        if (isEmpty()){
            return -1; // 或者报错
        }
        return elem[0];
    }

    
    //时间复杂度O（n*logn）
    // 空间复杂度O(1)
    // 堆排序
    private static void swap(int[] elem, int parent,int child){
        int tmp = elem[child];
        elem[child] = elem[parent];
        elem[parent] = tmp;
        /*child = parent;
        parent = (child - 1)/2;*/
    }
    public void heapSort(){
        // 先记录最后一个待排序的值的下标
        int end = usedSize - 1;
        while(end > 0){
            //开始交换两个的值
            swap(elem,0,end);
            //接下来开始调整这棵树
            // 先调整再让end--
            shiftDown(0,end);
            end -- ;
        }
    }
}
